package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * 979. 在二叉树中分配硬币
 *
 * 当前树需要的节点数 为 当前到父节点路径需要走多少。
 * @author feizns
 * @since 2020/3/14
 */
public class DistributeCoins {

    public static void main(String[] args) {
        System.out.println(distributeCoins(create()));
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(0);
        ret.left = new TreeNode(3);
        ret.right = new TreeNode(0);
        return ret;
    }

    public static int distributeCoins(TreeNode root) {
        distribute(root);
        return ans;
    }

    static int ans;

    private static int distribute(TreeNode root) {
        if ( root != null ) {
            int lef = distribute(root.left);
            int rig = distribute(root.right);
            int cut = lef + rig + root.val - 1;
            ans += Math.abs(cut);
            return cut;
        }
        return 0;
    }

}
